#ifndef MSC_LIST_H_M
#define MSC_LIST_H_M

#include "mem_base.h"
#include <stddef.h>
#include <string.h>

// 初始化头节点，把两个指针都指向自身
#define MS_LIST_INIT(q)     \
    (q)->prev = q;          \
    (q)->next = q

//判断是否是空队列
#define MS_LIST_EMPTY(h)        (h == (h)->next)

// 向队列的头插入数据节点
#define MS_LIST_PUSH_FRONT(h, i) \
    (i)->next = (h)->next;      \
    (i)->next->prev = i;        \
    (i)->prev = h;              \
    (h)->next = i

// 在节点的后面插入数据
#define MS_LIST_INSERT   MS_LIST_PUSH_FRONT


// 向队列的尾插入数据节点
// 在节点前插入数据
#define MS_LIST_PUSH_BACK(h, i) \
    (i)->prev = (h)->prev;      \
    (i)->prev->next = i;        \
    (i)->next = h;              \
    (h)->prev = i

// 获取队列的头指针
#define MS_LIST_FRONT(h)     ((h)->next)

// 获取队列的尾指针
#define MS_LIST_BACK(h)      ((h)->prev)

// 删除当前节点
#define MS_LIST_REMOVE(x)           \
    (x)->next->prev = (x)->prev;    \
    (x)->prev->next = (x)->next


// 拆分队列
#define MS_LIST_SPLIT(h, q, h2)  \
    (h2)->prev = (h)->prev;      \
    (h2)->prev->next = h2;       \
    (h2)->next = q;              \
    (h)->prev = (q)->prev;       \
    (h)->prev->next = h;         \
    (q)->prev = h2;


// 合并两个队列
#define MS_LIST_ADD(h, h2)  \
    (h)->prev->next = (h2)->next;   \
    (h2)->next->prev = (h)->prev;   \
    (h)->prev = (h2)->prev;         \
    (h)->prev->next = h;


// 从作为数据成员的结构访问到完整的数据节点
// q    ：指针，实际指向list节点对象
// type ：节点的类型，是一个名字
// link ：节点里数据成员的名字
#define MS_LIST_DATA(q, type, link)                                         \
    (type *) ((unsigned char *) q + offsetof(type, link))

//c list
typedef struct ms_list_item_s{
    struct ms_list_item_s* prev;
    struct ms_list_item_s* next;
    char p[0];
    //void* data;
}ms_list_item_t, *ms_list_item;

typedef ms_class_t ms_list_funs;
typedef struct ms_list_s {
    ms_alloc_t* ac;
    ms_list_item sentinel;//存放哨兵，哨兵的下一项才是表头， 哨兵的上一项才是表尾
    size_t size; //元素大小：0表示是指针, 整数，item的data直接赋值
    size_t count;
    ms_list_funs fs;
}ms_list_t, *ms_list;

//哨兵的prev指向表尾，哨兵的next指向表头，如果没有数据表头表尾都指向哨兵自己
//不对参数里的指针判断，可以增加数据计算效率
CPUBLIC ms_list ms_list_create(ms_alloc_t* ac, size_t size, ms_list_funs* fs) {
    if (!ac) {
        ac = ms_global_alloc();
    }
    ms_list l = (ms_list)ms_allocate(ac, sizeof(ms_list_t));
    if (l) {
        l->sentinel = (ms_list_item)ms_allocate(ac, sizeof(ms_list_item_t));
        if (l->sentinel) {
            l->ac = ac;
			MS_LIST_INIT(l->sentinel);
            if (size)
                l->size = size;
            else
                l->size = msc_size_ptr_;
            l->count = 0;
            ms_type_initclass(&l->fs, fs);
        }
        else {
            ac->deallocate(ac, l);
            l = NULL;
        }
	}
    return l;
}

CPUBLIC void ms_list_clear(ms_list l) {
    if (l) {
        ms_list_item i = l->sentinel->next;
        while (i != l->sentinel) {
            ms_list_item item = i;
            i = i->next;
            l->fs.destroy(item->p);
            ms_deallocate(l->ac, item);
        }
        l->sentinel->prev = l->sentinel->next = l->sentinel;
        l->count = 0;
    }
}

CPUBLIC void ms_list_destory(ms_list l) {
#ifdef _IF_NULL_
    if (l && l->sentinel) {
#endif
    ms_list_clear(l);
    ms_deallocate(l->ac, l->sentinel);
    ms_deallocate(l->ac, l);
#ifdef _IF_NULL_
    }
#endif
}
CPUBLIC bool ms_list_empty(ms_list l) {
    return (NULL == l) || MS_LIST_EMPTY(l->sentinel);
}
//元素个数
CPUBLIC size_t ms_list_size(ms_list l) {
#ifdef _IF_NULL_
    if (l) {
#endif
    return l->count;
#ifdef _IF_NULL_
    }
    return 0;
#endif
}

CPUBLIC bool ms_list_push_front(ms_list l, void* data) {
#ifdef _IF_NULL_
    if (l) {
#endif
    ms_list_item item = (ms_list_item)ms_allocate(l->ac, sizeof(ms_list_item_t)+l->size);
    if (item) {
        //赋值
		l->fs.construct(item->p);
		l->fs.copy(item->p, data);
		MS_LIST_PUSH_FRONT(l->sentinel, item);
        ++l->count;
        return true;
    }
#ifdef _IF_NULL_
    }
#endif
    return false;
}

CPUBLIC bool ms_list_push_back(ms_list l, void* data) {
#ifdef _IF_NULL_
    if (l) {
#endif
    ms_list_item item = (ms_list_item)ms_allocate(l->ac, sizeof(ms_list_item_t)+l->size);
    if (item) {
        //赋值
        l->fs.construct(item->p);
        l->fs.copy(item->p, data);
		MS_LIST_PUSH_BACK(l->sentinel, item);
        ++l->count;
        return true;
    }
#ifdef _IF_NULL_
    }
#endif
    return false;
}

CPUBLIC void ms_list_pop_front(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
		
        ms_list_item item = l->sentinel->next;
		if (item != l->sentinel) {
			MS_LIST_REMOVE(item);
			ms_deallocate(l->ac, item);
			--l->count;
		}       
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC void ms_list_pop_back(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
        ms_list_item item = l->sentinel->prev;
		if (item != l->sentinel) {
			MS_LIST_REMOVE(item);
			ms_deallocate(l->ac, item);
			--l->count;
		}       
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC void* ms_list_front(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
    return l->sentinel->next->p;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC void* ms_list_back(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
    return l->sentinel->prev->p;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_list_item ms_list_insert(ms_list l, ms_list_item parent, void* data) {
#ifdef _IF_NULL_
    if (l) {
#endif
        if (NULL == parent || parent == l->sentinel) {
            if (ms_list_push_front(l, data)) //直接插入到最前面
                return l->sentinel->next;
        }
        else {
            ms_list_item item = (ms_list_item)ms_allocate(l->ac, sizeof(ms_list_item_t)+l->size);
            if (item) {
                //赋值
                l->fs.construct(item->p);
                l->fs.copy(item->p, data);
				MS_LIST_INSERT(parent, item);
                ++l->count;
                return item;
            }
        }
#ifdef _IF_NULL_
    }
#endif
    return NULL;
}

CPUBLIC void ms_list_remove(ms_list l, ms_list_item item) {
#ifdef _IF_NULL_
    if (item && ms_list_size(l)) {
#endif
    ms_list_item p = l->sentinel->next;
    while (p != l->sentinel) {
        if (p == item) {
			MS_LIST_REMOVE(item);
            ms_deallocate(l->ac, p);
            --l->count;
            break;
        }
        p = p->next;
    }
#ifdef _IF_NULL_
    }
#endif
}

CPUBLIC ms_list_item ms_list_begin(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
        return l->sentinel->next;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
CPUBLIC ms_list_item ms_list_item_next(ms_list_item item) {
#ifdef _IF_NULL_
    if (item) {
#endif
        return item->next;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
CPUBLIC ms_list_item ms_list_end(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
        return l->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC ms_list_item ms_list_rbegin(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
        return l->sentinel->prev;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
CPUBLIC ms_list_item ms_list_item_rnext(ms_list_item item) {
#ifdef _IF_NULL_
    if (item) {
#endif
        return item->prev;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}
CPUBLIC ms_list_item ms_list_rend(ms_list l) {
#ifdef _IF_NULL_
    if (!ms_list_empty(l)) {
#endif
        return l->sentinel;
#ifdef _IF_NULL_
    }
    return NULL;
#endif
}

CPUBLIC void ms_list_item_swap(ms_list_item lt, ms_list_item rt) {
#ifdef _IF_NULL_
    if (lt && rt) {
#endif
    rt->prev->next = lt;
    lt->prev->next = rt;
    rt->next->prev = lt;
    lt->next->prev = rt;
    ms_list_item tmp = rt->prev;
    rt->prev = lt->prev;
    lt->prev = tmp;
    tmp = rt->next;
    rt->next = lt->next;
    lt->next = tmp;
#ifdef _IF_NULL_
    }
#endif
}

//列表排序
static inline void ms_list_sort_item(ms_list l, ms_list_item lt, ms_list_item rt, void* key, bool (*data_cmp)(void *left, void* right)) {
    //快速排序(非稳定)
    l->fs.copy(key, lt->p);//取关键项
    ms_list_item ld = lt, rd = rt;
    while (ld != rd) {
        //从右往左查比key小(大)的放左边ld
        while (ld != rd && !data_cmp(rd->p, key)) {
            rd = rd->prev;
        }
        if (ld == rd) break;
        //找到比key小的项
        //将rd的值放在左边
        l->fs.copy(ld->p, rd->p);
		ld = ld->next; //下一个
        
        //从左往右查比key大(小)的放右边
        while (ld != rd && data_cmp(ld->p, key)) {
            ld = ld->next;
        }
        if (ld == rd) break;
        //找到比key大的项
        //将ld的值放在右边
        l->fs.copy(rd->p, ld->p);
		rd = rd->prev; //前一个
    }
    l->fs.copy(ld->p,key);//最终key对应的位置
	//lt的值被改变
    if (ld != lt && lt != ld->prev) {
        ms_list_sort_item(l, lt, ld->prev, key, data_cmp);
    }
    if (ld != rt && rt != ld->next) {
        ms_list_sort_item(l, ld->next, rt, key, data_cmp);
    }
}

CPUBLIC void ms_list_sort(ms_list l, bool (*data_cmp)(void *left, void* right)) {
    if (NULL == l || l->count < 2) return;
    void* tmp = ms_allocate(l->ac, l->size);
    ms_list_sort_item(l, l->sentinel->next, l->sentinel->prev, tmp, data_cmp);
    ms_deallocate(l->ac, tmp);
}


CPUBLIC void ms_list_sort_default(ms_list l) {
    ms_list_sort(l, ms_type_less);
}
//有序插入
CPUBLIC bool ms_list_insert_sort(ms_list SortedList, void* data, bool (*data_cmp)(void *left, void* right)) {
#ifdef _IF_NULL_
    if (SortedList) {
#endif
        ms_list_item_t* parent = SortedList->sentinel;
        while (parent->next != SortedList->sentinel && data_cmp(parent->next->p, data)) {
            parent = parent->next;
        }
        if (parent == SortedList->sentinel) {
            return ms_list_push_front(SortedList, data);
        }
        return ms_list_insert(SortedList, parent, data);
#ifdef _IF_NULL_
    }
#endif
    return false;
}
#endif //MSC_LIST_H_M
